package CommonClass;

import java.util.Arrays;
import java.util.List;

public class Common {
    /**
     * 链表
     */
    public static class ListNode {
        public int val;
        public ListNode next;

        public ListNode() {
        }

        public ListNode(int val) {
            this.val = val;
        }

        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }


    /**
     * 二叉树
     */
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode() {
        }

        public TreeNode(int val) {
            this.val = val;
        }

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static class Node {
        public int val;
        public List<Node> children;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, List<Node> _children) {
            val = _val;
            children = _children;
        }
    }

    public static class UF {
        private int count;
        private int[] parent;
        private int[] size;

        public UF(int n) {
            this.count = n;
            parent = new int[n];
            size = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }
        public void union(int p, int q) {
            int rootP = find(p);
            int rootQ = find(q);
            if (rootP == rootQ) return ;
            // 平衡性优化
            if (size[rootP] < size[rootQ]) {
                parent[rootP] = rootQ;
                size[rootQ] += size[rootP];
            } else {
                parent[rootQ] = rootP;
                size[rootP] += size[rootQ];
            }
            this.count--;
        }
        public boolean isConnected(int p, int q) {
            int rootP = find(p);
            int rootQ = find(q);
            return rootP == rootQ;
        }
        /*
        count用来返回并查集中簇的数量
         */
        public int count() {
            return this.count;
        }
        private int find(int x) {
            // 路径压缩
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        /*
        找出并查集中一个最大的簇的大小
         */
        public int getMaxConnectSize() {
            int maxSize = 0;
            for (int i = 0; i < parent.length; i++) {
                if (i == parent[i]) {
                    maxSize = Math.max(maxSize, size[i]);
                }
            }
            return maxSize;
        }

        /*
        拿到对应代表节点所代表簇的大小的方法
         */
        public int getSize(int x) {
            int root = find(x);
            return size[root];
        }
    }



    /**
     * 由头部开始打印一个ListNode
     *
     * @param l 链表的头部
     */
    public static void printList(ListNode l) {
        while (l != null) {
            if (l.next != null) {
                System.out.print(l.val + " -> ");
            } else {
                System.out.println(l.val);
            }
            l = l.next;
        }
    }

    /**
     * 生成一个ListNode
     *
     * @param a 一个int[]的数组
     * @return 获取ListNode的头部
     */
    public static ListNode generateList(int[] a) {

        if (a.length == 0) {
            return null;
        }

        ListNode head = new ListNode(a[0]);
        ListNode tail = head;
        for (int i = 1; i < a.length; i++) {
            tail.next = new ListNode(a[i]);
            tail = tail.next;
        }

        return head;
    }

    /**
     * 打印一个二维数组
     *
     * @param m 二维数组
     */
    public static void printMatrix(int[][] m) {
        for (int[] ins : m) {
            System.out.println(Arrays.toString(ins));
        }
    }

    public static void printMatrix(boolean[][] m) {
        for (boolean[] ins : m) {
            System.out.println(Arrays.toString(ins));
        }
    }
}
